package maximumProductOfWordLengths;

import java.util.Arrays;
import java.util.Comparator;

public class Solution {
    public int maxProduct(String[] words) {
        Arrays.sort(words, new cmp());
        int ans=0;
        int bm[]=new int[words.length];
        for (int i=0;i<words.length;i++)
        	bm[i]=trans(words[i]);
        for (int i=0;i<words.length;i++){
        	for (int j=i+1;j<words.length;j++)
        		if (((bm[i]&bm[j])==0) && (words[i].length()*words[j].length()>ans))
        		 ans=words[i].length()*words[j].length();
        		else if (words[i].length()*words[j].length()<ans) break;
        }
        return ans;
    }
    private int trans(String string) {

    	int result=0;
		for (int i=0;i<string.length();i++)
			result=result|(1<<(string.charAt(i)-'a'));

		return result;
	}
	class cmp implements Comparator<String>{

		@Override
		public int compare(String o1, String o2) {
			return (o2.length()-o1.length());
		}
	}
	public static void main(String args[]){
		Solution so=new Solution();
		String[] words={"ccd","accaceddeeeaefc","bcaffa","bbcfafbb","accacfebbabbeedfbfdb","beddecbffcdaededdaefdedfdea","cf","ddafdcbd","bbafacebacaefdaffccebddff","ebccffcddbeddccacceccaec","becfbfdccdfdeadfbfaddbcded","cbabeaaeabefedbaeaedc","dfadbbdbead","cafaefdcd","eccdbfceafeeeacfcddc","dbabbcdbb","abfbfbffcbebde","cfaadaa","fc","faebcabb","adbacebabcaaccbdeaffff","aeaefccf","dbacbeeabdbcdfccabebaecfef","ecdadeefcaddffaececffa","defcabf","abbcecbccbdaebaecaefabed","dfeeebcbaaefc","aecccbcbbdddb","dcfabacec","fccfbacbacddeaaea","dfdbfacbacbecb","cbfeebdbfecb","cffaacacbde","aafd","bdcebbbebd","afeffadcfcdacfba","dafeefbcdfaffcfacee","dcbbebfbedafedcdbab","cafaf","bcbcccfdebdd","efaaaacccff","cffbead","ebcfccfcddffdec","fffdfdcec","beeafefbdfa","cdfdbccfbaaeffcabab","ddadcbabbcb","decfaeabbecebaebeaddedae","cdcbfffbebae","aeccefcbcbbddfdc","ffefedaf","cddbabccafaffeafeedcbedbdad","eddeeccfedcefadfdfebfacb","aca","ffdcafaddcddf","ef","bbbbffe","ffccfebabaadcffacbbb","cbdeddfddffacbeeeebafebabda","ddeecb","cffdc","edcffcebadf","becbcadcafddcfbbeeddbfffcab","abcbaceeaeaddd","cfeffceebfaeefadaaccfa","eaccddb","caeafbfafecd","becaafdbaadbfecfdfde","ecabaaeafbfbcbadaac","bdcdffcfaeebeedfdfddfaf","dbbfbaeecbfcdebad","cceecddeeecdbde","beec","adbcfdbfdbccdcffffbcffbec","bbbbfe","cdaedaeaad","dadbfeafadd","fcacaaebcedfbfbcddfc","ceecfedceac","dada","ccfdaeffbcfcc","eadddbbbdfa","beb","fcaaedadabbbeacabefdabe","dfcddeeffbeec","defbdbeffebfceaedffbfee","cffadadfbaebfdbadebc","fbbadfccbeffbdeabecc","bdabbffeefeccb","bdeeddc","afcbacdeefbcecff","cfeaebbbadacbced","edfddfedbcfecfedb","faed","cbcdccfcbdebabc","efb","dbddadfcddbd","fbaefdfebeeacbdfbdcdddcbefc","cbbfaccdbffde","adbcabaffebdffad"};
		System.out.println(so.maxProduct(words));
	}
}
/* 
 * 318. Maximum Product of Word Lengths
 * bimMap=位图存储？
 * 位运算博大精深系列（话说比起炮兵阵地和八皇后的位数算还是弱了。。没办法，当年是个弱鸡，现在单细胞一枚）
 * O（n^2)
 * 时间复杂度是定死的。。位运算用于优化（排序也是优化，不过效果看脸）。
 * 任意两个合法字符串不能出现相同字母，故一个字符串的存储信息简化为一个2^26的int+字符串长度
 * 存储完毕之后for一遍就行
 * PS：话说这东西不用位运算的化也要特殊数据才能卡死吧。。严重怀疑是不是排序优化也能过233333
 */
